package Graph;

import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

public class Dijkstra {
    /**
     * @param matrix 　邻接矩阵；没有边连接用Integer.MAX_VALUE表示
     * @return 二维数组array，array[0]是距离数组dist，array[1]是路径数组path
     */
    public int[][] solve(int[][] matrix, int source) {
        int n = matrix.length;
        boolean[] visited = new boolean[n];
        int[] dist = new int[n]; // source到各顶点的最短距离
        int[] path = new int[n]; // 记录了source到各顶点的最短路径；path[v]表示source->v的最短路径上，v的前一个顶点是path[v]
        for (int i = 0; i < n; i++) {
            dist[i] = matrix[source][i];
            if (dist[i] < Integer.MAX_VALUE) path[i] = source;
            else path[i] = -1;
        }
        visited[source] = true;
        for (int i = 1; i <= n - 1; i++) {
            int pickedVertex = -1, minDist = Integer.MAX_VALUE;

            // 遍历未确定最短路径的顶点，选取dist最小的一个
            for (int j = 0; j < n; j++) {
                if (!visited[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    pickedVertex = j;
                }
            }

            visited[pickedVertex] = true; // 最短路径确定

            // 更新其他顶点的最短路径
            for (int j = 0; j < n; j++) {
                if (!visited[j] && matrix[pickedVertex][j] < Integer.MAX_VALUE &&
                        dist[j] > dist[pickedVertex] + matrix[pickedVertex][j]) {
                    dist[j] = dist[pickedVertex] + matrix[pickedVertex][j];
                    path[j] = pickedVertex;
                }
            }
        }

        // 浅拷贝
        int[][] ret = new int[2][];
        ret[0] = dist;
        ret[1] = path;

        return ret;
    }

    /**
     * 从Dijkstra算法产生的path数组中解析source到dest的路径，返回路径上的每个顶点（包括source和dest）
     */
    public ArrayList<Integer> parsePath(int[] path, int source, int dest) {
        ArrayList<Integer> ret = new ArrayList<>();
        if (source == dest) {
            ret.add(source);
            return ret;
        }
        if (path[dest] == -1) return null;

        int ptr = dest;
        Deque<Integer> stack = new ArrayDeque<>();
        while (ptr != source) {
            stack.push(ptr);
            ptr = path[ptr];
        }
        stack.push(source);

        while (!stack.isEmpty()) ret.add(stack.pop());

        return ret;
    }
}
